#define _CRT_SECURE_NO_WARNINGS


//
//#include <iostream>
//#include <algorithm>
//using namespace std;
//
//const int N = 100010, M = 31 * N;
//int idx, n, son[M][2], a[N];
//
//void insert(int x)
//{
//    int q = 0;
//    for (int i = 30; i >= 0; i--)
//    {
//        int u = x >> i & 1;
//        if (!son[q][u]) son[q][u] = ++idx;
//        q = son[q][u];
//    }
//}
//
//int query(int x)
//{
//    int q = 0, res = 0;
//    for (int i = 30; i >= 0; i--)
//    {
//        int u = x >> i & 1;
//        if (son[q][!u])
//        {
//            res = res * 2 + !u;
//            q = son[q][!u];
//        }
//        else
//        {
//            res = res * 2 + u;
//            q = son[q][u];
//        }
//    }
//
//    return res;
//}
//
//int main()
//{
//    cin >> n;
//    for (int i = 0; i < n; i++) cin >> a[i];
//
//    int res = 0;
//    for (int i = 0; i < n; i++)
//    {
//        insert(a[i]);
//        int t = query(a[i]);
//        res = max(res, a[i] ^ t);
//    }
//
//    cout << res << endl;
//
//    return 0;
//}

//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int n, m, _size[N], p[N];
//
//int find(int x)
//{
//    if (p[x] != x) p[x] = find(p[x]);
//    return p[x];
//}
//
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++)
//    {
//        p[i] = i;
//        _size[i] ++;
//    }
//
//    while (m--)
//    {
//        int a, b;
//        string op;
//        cin >> op;
//
//        if (op == "C")
//        {
//            cin >> a >> b;
//            if (find(a) == find(b)) continue;
//            _size[find(b)] += _size[find(a)];
//            p[find(a)] = find(b);
//        }
//        else if (op == "Q1")
//        {
//            cin >> a >> b;
//            if (find(a) == find(b)) cout << "Yes" << endl;
//            else cout << "No" << endl;
//        }
//        else
//        {
//            cin >> a;
//            cout << _size[find(a)] << endl;
//        }
//    }
//
//    return 0;
//}


//
//#include <iostream>
//using namespace std;
//
//const int N = 50010;
//int n, k, p[N], d[N];
//
//int find(int x)
//{
//    if (p[x] != x)
//    {
//        int t = find(p[x]);
//        d[x] += d[p[x]];
//        p[x] = t;
//    }
//
//    return p[x];
//}
//
//int main()
//{
//    cin >> n >> k;
//    for (int i = 1; i <= n; i++) p[i] = i;
//
//    int res = 0;
//    while (k--)
//    {
//        int t, x, y;
//        cin >> t >> x >> y;
//
//        if (x > n || y > n) res++;
//        else
//        {
//            int px = find(x), py = find(y);
//            if (t == 1)
//            {
//                if (px == py && (d[x] - d[y]) % 3) res++;
//                else if (px != py)
//                {
//                    p[px] = py;
//                    d[px] = d[y] - d[x];
//                }
//            }
//            else
//            {
//                if (px == py && (d[x] - d[y] - 1) % 3) res++;
//                else if (px != py)
//                {
//                    p[px] = py;
//                    d[px] = d[y] - d[x] + 1;
//                }
//            }
//        }
//    }
//
//    cout << res << endl;
//
//    return 0;
//}

//
//#include <iostream>
//#include <string.h>
//using namespace std;
//
//const int N = 100003;
//int h[N], ne[N], e[N], idx;
//int n;
//
//void insert(int x)
//{
//    int t = (x % N + N) % N;
//
//    e[idx] = x;
//    ne[idx] = h[t];
//    h[t] = idx++;
//}
//
//bool query(int x)
//{
//    int t = (x % N + N) % N;
//    for (int i = h[t]; i != -1; i = ne[i])
//        if (e[i] == x) return true;
//
//    return false;
//}
//
//int main()
//{
//    cin >> n;
//
//    memset(h, -1, sizeof(h));
//
//    while (n--)
//    {
//        string op;
//        int x;
//        cin >> op >> x;
//        if (op == "I")
//        {
//            insert(x);
//        }
//        else
//        {
//            if (query(x)) cout << "Yes" << endl;
//            else cout << "No" << endl;
//        }
//    }
//
//    return 0;
//}